package Midium;

import java.util.*;

//15.三数之和
//思路：寻找两个数b和c使得b+c==-a
public class Solution15 {
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> set = new HashSet<>();
        int a, b, c;
        for (int i = 0; i < nums.length - 2; i++) {
            a = (-1) * nums[i];
            for (int j = i + 1; j < nums.length - 1; j++) {
                b = nums[j];
                int u = j + 1, v = nums.length - 1;
                for (int k; u <= v; ) {
                    k = (u + v + 1 ) / 2;
                    c = nums[k];
                    if (a == b + c) {
//                        int[] arr = new int[]{nums[i], b, c};
//                        Arrays.sort(arr);
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        set.add(list);
                        break;
                    }else if(k==v)v--; // 二分查找结束循环的精髓语句
                    else if (b + c < a) {
                        u = k;
                    } else {
                        v = k;
                    }
                }
            }
        }
        return new ArrayList<>(set);
    }

    public static void main(String[] args) {
        List<List<Integer>> list = threeSum(new int[]{-1,0,1,2,-1,4});
        for (List<Integer> l : list) {
            for (int a : l) {
                System.out.print(a + " ");
            }
            System.out.println("");
        }
    }
}
